{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Intersection of Two Linked Lists LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getIntersectionNode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #链表相交"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个单链表的头节点 <code>headA</code> 和 <code>headB</code> ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 <code>null</code> 。</p>\n",
    "\n",
    "<p>图示两个链表在节点 <code>c1</code> 开始相交<strong>：</strong></p>\n",
    "\n",
    "<p><a href=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png\" target=\"_blank\"><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png\" style=\"height: 130px; width: 400px;\" /></a></p>\n",
    "\n",
    "<p>题目数据 <strong>保证</strong> 整个链式结构中不存在环。</p>\n",
    "\n",
    "<p><strong>注意</strong>，函数返回结果后，链表必须 <strong>保持其原始结构</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><a href=\"https://assets.leetcode.com/uploads/2018/12/13/160_example_1.png\" target=\"_blank\"><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_1.png\" style=\"height: 130px; width: 400px;\" /></a></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3\n",
    "<strong>输出：</strong>Intersected at '8'\n",
    "<strong>解释：</strong>相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。\n",
    "从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。\n",
    "在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><a href=\"https://assets.leetcode.com/uploads/2018/12/13/160_example_2.png\" target=\"_blank\"><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_2.png\" style=\"height: 136px; width: 350px;\" /></a></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1\n",
    "<strong>输出：</strong>Intersected at '2'\n",
    "<strong>解释：</strong>相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。\n",
    "从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。\n",
    "在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><a href=\"https://assets.leetcode.com/uploads/2018/12/13/160_example_3.png\" target=\"_blank\"><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_3.png\" style=\"height: 126px; width: 200px;\" /></a></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2\n",
    "<strong>输出：</strong>null\n",
    "<strong>解释：</strong>从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。\n",
    "由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。\n",
    "这两个链表不相交，因此返回 null 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>listA</code> 中节点数目为 <code>m</code></li>\n",
    "\t<li><code>listB</code> 中节点数目为 <code>n</code></li>\n",
    "\t<li><code>0 <= m, n <= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 <= Node.val <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 <= skipA <= m</code></li>\n",
    "\t<li><code>0 <= skipB <= n</code></li>\n",
    "\t<li>如果 <code>listA</code> 和 <code>listB</code> 没有交点，<code>intersectVal</code> 为 <code>0</code></li>\n",
    "\t<li>如果 <code>listA</code> 和 <code>listB</code> 有交点，<code>intersectVal == listA[skipA + 1] == listB[skipB + 1]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能否设计一个时间复杂度 <code>O(n)</code> 、仅用 <code>O(1)</code> 内存的解决方案？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [intersection-of-two-linked-lists-lcci](https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [intersection-of-two-linked-lists-lcci](https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['8\\n[4,1,8,4,5]\\n[5,0,1,8,4,5]\\n2\\n3', '2\\n[0,9,1,2,4]\\n[3,2,4]\\n3\\n1', '0\\n[2,6,4]\\n[1,5]\\n3\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        l1 = 0\n",
    "        l2 = 0\n",
    "        cur = headA\n",
    "        while cur:\n",
    "            l1 += 1\n",
    "            cur = cur.next\n",
    "        cur = headB\n",
    "        while cur:\n",
    "            l2 += 1\n",
    "            cur = cur.next\n",
    "        cur1, cur2, diff = (headA, headB, l1 - l2) if l1 > l2 else (headB, headA, l2 - l1)\n",
    "        while diff:\n",
    "            cur1 = cur1.next\n",
    "            diff -= 1\n",
    "        while cur1 and cur2:\n",
    "            if cur1 == cur2:\n",
    "                return cur1\n",
    "            cur1 = cur1.next\n",
    "            cur2 = cur2.next\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        # 将两个链表的尾对齐，公共结点必定出现在重叠的部分，且对齐。\n",
    "        len_a, len_b = 0, 0\n",
    "        cur = headA\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            len_a += 1\n",
    "        cur = headB\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            len_b += 1\n",
    "\n",
    "        curA, curB = headA, headB\n",
    "        if len_a > len_b:     # 让curB为最长链表的头，lenB为其长度\n",
    "            curA, curB = curB, curA\n",
    "            len_a, len_b = len_b, len_a\n",
    "\n",
    "        for _ in range(len_b - len_a):\n",
    "            curB = curB.next\n",
    "            # 使两者末尾对齐\n",
    "        while curA:\n",
    "            if curA == curB:\n",
    "                return curA\n",
    "            else:\n",
    "                curA = curA.next\n",
    "                curB = curB.next\n",
    "\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        lenA, lenB = 0,0\n",
    "        \n",
    "        cur = headA\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            lenA += 1\n",
    "        cur = headB\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            lenB += 1\n",
    "\n",
    "        curA, curB = headA, headB\n",
    "        if lenA > lenB:\n",
    "            curA, curB = curB, curA\n",
    "            lenA, lenB = lenB, lenA\n",
    "        \n",
    "        for _ in range(lenB - lenA):\n",
    "            curB = curB.next\n",
    "        while curB:\n",
    "            if curA == curB:\n",
    "                return curA\n",
    "            else:\n",
    "                curA = curA.next\n",
    "                curB = curB.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        h1,h2 = headA,headB\n",
    "\n",
    "        while(h1 != h2):\n",
    "            if h1 == None:\n",
    "                h1 = headB\n",
    "            else:\n",
    "                h1 = h1.next\n",
    "\n",
    "            if  h2 == None:\n",
    "                h2 = headA\n",
    "            else:\n",
    "                h2 = h2.next\n",
    "\n",
    "        \n",
    "        return h1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        curA = headA\n",
    "        curB = headB\n",
    "        sizeA = 0\n",
    "        sizeB = 0\n",
    "        while(curA != None):\n",
    "            sizeA += 1\n",
    "            curA = curA.next\n",
    "        while(curB != None):\n",
    "            sizeB += 1\n",
    "            curB = curB.next\n",
    "\n",
    "        curA = headA\n",
    "        curB = headB\n",
    "        if sizeA < sizeB:\n",
    "            subsize = sizeB - sizeA\n",
    "            while(subsize):\n",
    "                curB = curB.next\n",
    "                subsize -= 1\n",
    "        else:\n",
    "            subsize = sizeA - sizeB\n",
    "            while(subsize):\n",
    "                curA = curA.next\n",
    "                subsize -= 1\n",
    "        while(curA != None):\n",
    "            if curA == curB:\n",
    "                return curA\n",
    "            curA = curA.next\n",
    "            curB = curB.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        ha, hb = headA, headB\n",
    "        while ha != hb:\n",
    "            ha = headB if ha == None else ha.next\n",
    "            hb = headA if hb == None else hb.next\n",
    "        return ha"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        curA = headA\n",
    "        curB = headB\n",
    "        while curA and curB:\n",
    "            curA = curA.next\n",
    "            curB = curB.next\n",
    "        count = 0\n",
    "        A = headA\n",
    "        B = headB\n",
    "        if curA:\n",
    "            A = headA\n",
    "            B = headB\n",
    "            while curA:\n",
    "                count += 1\n",
    "                curA = curA.next\n",
    "        else:\n",
    "            A = headB\n",
    "            B = headA\n",
    "            while curB:\n",
    "                count += 1\n",
    "                curB = curB.next\n",
    "        while count:\n",
    "            A = A.next\n",
    "            count -= 1\n",
    "\n",
    "        while A:\n",
    "            if A == B:\n",
    "                return A\n",
    "            A = A.next\n",
    "            B = B.next\n",
    "        return None\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        # 将两个链表的尾对齐，公共结点必定出现在重叠的部分，且对齐。\n",
    "        len_a, len_b = 0, 0\n",
    "        cur = headA\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            len_a += 1\n",
    "        cur = headB\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            len_b += 1\n",
    "\n",
    "        curA, curB = headA, headB\n",
    "        if len_a > len_b:     # 让curB为最长链表的头，lenB为其长度\n",
    "            curA, curB = curB, curA\n",
    "            len_a, len_b = len_b, len_a\n",
    "\n",
    "        for _ in range(len_b - len_a):\n",
    "            curB = curB.next\n",
    "            # 使两者末尾对齐\n",
    "        while curA:\n",
    "            if curA == curB:\n",
    "                return curA\n",
    "            else:\n",
    "                curA = curA.next\n",
    "                curB = curB.next\n",
    "\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        lenA, lenB = 0, 0\n",
    "        cur = headA\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            lenA += 1\n",
    "        cur = headB\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            lenB += 1\n",
    "        curA, curB = headA, headB\n",
    "        if lenA > lenB: # 一直让curB是大的\n",
    "            lenA, lenB = lenB, lenA\n",
    "            curA,curB = curB, curA\n",
    "        for i in range(lenB-lenA):\n",
    "            curB = curB.next\n",
    "        while curA:\n",
    "            if curA == curB:\n",
    "                return curA\n",
    "            else:\n",
    "                curA = curA.next\n",
    "                curB = curB.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        cur_a,cur_b=headA,headB\n",
    "        while cur_a!=cur_b:\n",
    "            if cur_a:\n",
    "                cur_a=cur_a.next\n",
    "            else:\n",
    "                cur_a=headB\n",
    "            if cur_b:\n",
    "                cur_b=cur_b.next\n",
    "            else:\n",
    "                cur_b=headA\n",
    "        return cur_a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        cur=headA\n",
    "        lenA=0\n",
    "        while(cur!=None):\n",
    "            cur=cur.next\n",
    "            lenA+=1\n",
    "        cur=headB\n",
    "        lenB=0\n",
    "        while(cur!=None):\n",
    "            cur=cur.next\n",
    "            lenB+=1\n",
    "        curA=headA\n",
    "        curB=headB\n",
    "        if(lenA>lenB):\n",
    "            temp1=curB\n",
    "            curB=curA\n",
    "            curA=temp1\n",
    "            temp2=lenB\n",
    "            lenB=lenA\n",
    "            lenA=temp2\n",
    "        for _ in range(lenB-lenA):\n",
    "            curB=curB.next\n",
    "        while(curA!=None):\n",
    "            if(curA==curB):\n",
    "                return curA\n",
    "            else:\n",
    "                curA = curA.next \n",
    "                curB = curB.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        node = headA\n",
    "        c_a = 0\n",
    "        while node:\n",
    "            node = node.next\n",
    "            c_a += 1\n",
    "        node = headB\n",
    "        c_b = 0\n",
    "        while node:\n",
    "            node = node.next\n",
    "            c_b += 1\n",
    "        if c_a > c_b:\n",
    "            step = c_a - c_b\n",
    "            while step:\n",
    "                headA = headA.next\n",
    "                step -= 1\n",
    "        elif c_a < c_b:\n",
    "            step = c_b - c_a\n",
    "            while step:\n",
    "                headB = headB.next\n",
    "                step -= 1\n",
    "        while headA:\n",
    "            if headA == headB:\n",
    "                return headA\n",
    "            else:\n",
    "                headA = headA.next\n",
    "                headB = headB.next\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:\n",
    "            return None\n",
    "        else:\n",
    "            cur = headA\n",
    "            lenA = 0\n",
    "            while cur:\n",
    "                cur = cur.next\n",
    "                lenA+=1\n",
    "            cur = headB\n",
    "            lenB = 0\n",
    "            while cur:\n",
    "                cur = cur.next\n",
    "                lenB+=1\n",
    "            if lenA>=lenB:\n",
    "                d = lenA-lenB\n",
    "                curA = headA\n",
    "                for i in range(d):\n",
    "                    curA = curA.next\n",
    "                curB = headB\n",
    "                while curA!=curB:\n",
    "                    curA=curA.next\n",
    "                    curB=curB.next\n",
    "            else:\n",
    "                d = lenB-lenA\n",
    "                curB = headB\n",
    "                for i in range(d):\n",
    "                    curB = curB.next\n",
    "                curA = headA  \n",
    "                while curA!=curB:\n",
    "                    curA=curA.next\n",
    "                    curB=curB.next           \n",
    "\n",
    "            return curA\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        lenA, lenB = 0,0\n",
    "        dummyheadA = ListNode()\n",
    "        dummyheadA.next = headA\n",
    "        dummyheadB = ListNode()\n",
    "        dummyheadB.next = headB\n",
    "        curA = dummyheadA\n",
    "        curB = dummyheadB\n",
    "        while curA.next != None:\n",
    "            curA = curA.next\n",
    "            lenA += 1\n",
    "        while curB.next != None:\n",
    "            curB = curB.next\n",
    "            lenB += 1    \n",
    "        cha = abs(lenA - lenB)\n",
    "        curA = dummyheadA\n",
    "        curB = dummyheadB\n",
    "        if lenA <= lenB:\n",
    "            while cha > 0:\n",
    "                curB = curB.next\n",
    "                cha -= 1\n",
    "            while curA != None:\n",
    "                if curA != curB:\n",
    "                    curA = curA.next\n",
    "                    curB = curB.next\n",
    "                elif curA == curB:\n",
    "                    return curA\n",
    "            if curA == None:\n",
    "                return None\n",
    "        if lenA > lenB:\n",
    "            while cha > 0:\n",
    "                curA = curA.next\n",
    "                cha -= 1\n",
    "            while curB != None:\n",
    "                if curA != curB:\n",
    "                    curA = curA.next\n",
    "                    curB = curB.next\n",
    "                elif curA == curB:\n",
    "                    return curB\n",
    "            if curB == None:\n",
    "                return(None)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        d = {}\n",
    "        dummy_head = headB\n",
    "        while headA:\n",
    "            d[headA] = 1\n",
    "            headA = headA.next\n",
    "        while headB:\n",
    "            if headB in d:\n",
    "                return headB\n",
    "            else:\n",
    "                headB = headB.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        # 法1 哈希表\n",
    "        pA = headA\n",
    "        pB = headB\n",
    "        hashset = set()\n",
    "        while pA:\n",
    "            hashset.add(pA)\n",
    "            pA = pA.next\n",
    "        while pB:\n",
    "            if pB in hashset:\n",
    "                return pB\n",
    "            pB = pB.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        # 双指针\n",
    "        # cur1 = headA\n",
    "        # cur2 = headB\n",
    "        # while cur1 != cur2:\n",
    "        #     cur1 = cur1.next if cur1 else headB\n",
    "        #     cur2 = cur2.next if cur2 else headA\n",
    "        # return cur1\n",
    "\n",
    "        # hash\n",
    "\n",
    "        hashset = set()\n",
    "        while headA:\n",
    "            hashset.add(headA)\n",
    "            headA = headA.next\n",
    "        while headB:\n",
    "            if headB in hashset:\n",
    "                return headB\n",
    "            else:\n",
    "                headB = headB.next\n",
    "        return None\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        cur = headA\n",
    "        dict = set()\n",
    "        while cur != None:\n",
    "            dict.add(cur)\n",
    "            cur = cur.next\n",
    "        cur = headB\n",
    "        while cur != None:\n",
    "            if cur in dict:\n",
    "                return cur\n",
    "            cur = cur.next\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:\n",
    "            return None\n",
    "        node_set = set()\n",
    "        while headA:\n",
    "            node_set.add(headA)\n",
    "            headA = headA.next\n",
    "        while headB:\n",
    "            if headB in node_set:\n",
    "                return headB\n",
    "            headB = headB.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        dict_1 = {}\n",
    "        current_1, current_2 = headA, headB\n",
    "        while current_1:\n",
    "            dict_1[current_1] = 1\n",
    "            current_1 = current_1.next\n",
    "#        print(dict_1)\n",
    "        while current_2:\n",
    "            if current_2 in dict_1:\n",
    "                return current_2\n",
    "            else:\n",
    "                current_2 = current_2.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        seen = set()\n",
    "        while headA:\n",
    "            seen.add(headA)\n",
    "            headA = headA.next \n",
    "        while headB:\n",
    "            if headB in seen:\n",
    "                return headB\n",
    "            headB = headB.next \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        # lenA, lenB = 0, 0\n",
    "        # cur = headA\n",
    "        # while cur:         # 求链表A的长度\n",
    "        #     cur = cur.next \n",
    "        #     lenA += 1\n",
    "        # cur = headB \n",
    "        # while cur:         # 求链表B的长度\n",
    "        #     cur = cur.next \n",
    "        #     lenB += 1\n",
    "        # curA, curB = headA, headB\n",
    "        # if lenA > lenB:     # 让curB为最长链表的头，lenB为其长度\n",
    "        #     curA, curB = curB, curA\n",
    "        #     lenA, lenB = lenB, lenA \n",
    "        # for _ in range(lenB - lenA):  # 让curA和curB在同一起点上（末尾位置对齐）\n",
    "        #     curB = curB.next \n",
    "        # while curA:         #  遍历curA 和 curB，遇到相同则直接返回\n",
    "        #     if curA == curB:\n",
    "        #         return curA\n",
    "        #     else:\n",
    "        #         curA = curA.next \n",
    "        #         curB = curB.next\n",
    "        # return None\n",
    "        if not headA or not headB:\n",
    "            return None\n",
    "        dic = set()\n",
    "        while headA:\n",
    "            dic.add(headA)\n",
    "            headA = headA.next\n",
    "        while headB:\n",
    "            if headB in dic:\n",
    "                return headB\n",
    "            headB = headB.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        m=set()\n",
    "        a=headA\n",
    "        while a is not None:\n",
    "            m.add(a)\n",
    "            a=a.next\n",
    "        b= headB\n",
    "        while b is not None:\n",
    "            if b in m:\n",
    "                return b\n",
    "            b = b.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        look_set=set()\n",
    "        while headA is not None:\n",
    "            look_set.add(headA)\n",
    "            headA=headA.next\n",
    "        while headB is not None:\n",
    "            if headB in look_set:\n",
    "                return headB\n",
    "            headB=headB.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:\n",
    "            return None\n",
    "        s = set()\n",
    "        while headA:\n",
    "            s.add(headA)\n",
    "            headA = headA.next\n",
    "        while headB:\n",
    "            if headB in s:\n",
    "                return headB\n",
    "            headB = headB.next\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        s = set()\n",
    "        cur = headA\n",
    "        while(cur != None):\n",
    "            s.add(cur)\n",
    "            cur = cur.next\n",
    "        cur = headB\n",
    "        while((cur != None) and (cur not in s)):\n",
    "            cur = cur.next\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        a=set()\n",
    "        while headA:\n",
    "            a.add(headA)\n",
    "            headA=headA.next\n",
    "        while headB:\n",
    "            if headB in a:\n",
    "                return headB\n",
    "                break\n",
    "            else:headB=headB.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        visited = set()\n",
    "        curA = headA\n",
    "        while curA:\n",
    "            visited.add(curA)\n",
    "            curA = curA.next\n",
    "        curB = headB\n",
    "        while curB:\n",
    "            if curB in visited:\n",
    "                return curB\n",
    "            else:\n",
    "                curB = curB.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        s = set()\n",
    "        temp = headA\n",
    "        while temp:\n",
    "            s.add(temp)\n",
    "            temp = temp.next\n",
    "        temp = headB\n",
    "        while temp:\n",
    "            if temp in s:\n",
    "                return temp\n",
    "            temp = temp.next\n",
    "        return None\n",
    "\n",
    "        \"\"\" listA = []\n",
    "        temp = headA\n",
    "\n",
    "        while temp:\n",
    "            listA.append(temp)\n",
    "            temp = temp.next\n",
    " \n",
    "        temp = headB\n",
    "        while temp:\n",
    "            if temp in listA:\n",
    "                return temp\n",
    "            temp = temp.next\n",
    "\n",
    "        return None \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        dic1={}\n",
    "        cur=headA\n",
    "        while cur:\n",
    "            \n",
    "            dic1[cur]=cur.next\n",
    "            cur=cur.next\n",
    "\n",
    "        dic2={}\n",
    "        cur=headB\n",
    "        while cur:\n",
    "            dic2[cur]=0\n",
    "            cur=cur.next\n",
    "\n",
    "        for key,item in dic1.items():\n",
    "            if key in dic2:\n",
    "                return key\n",
    "\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "\n",
    "        if not headA or not headB:\n",
    "            return\n",
    "        \n",
    "        dic = dict()\n",
    "        i = 0\n",
    "        \n",
    "        while headA:\n",
    "            dic[headA] = i\n",
    "            headA = headA.next\n",
    "            i+=1\n",
    "        \n",
    "        while headB:\n",
    "            if headB in dic:\n",
    "                return headB\n",
    "            else:\n",
    "                headB = headB.next\n",
    "\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        tid = {}\n",
    "        hA, hB = headA, headB\n",
    "        while hA:\n",
    "            # 节点地址是否一致\n",
    "            tid[id(hA)] = hA.val\n",
    "            hA = hA.next\n",
    "        \n",
    "        while hB:\n",
    "            if id(hB) in tid:\n",
    "                return ListNode(hB.val)\n",
    "            hB = hB.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        dic = set()\n",
    "        cur_a = headA\n",
    "        cur_b = headB\n",
    "        while cur_a:\n",
    "            dic.add(cur_a)\n",
    "            cur_a = cur_a.next\n",
    "        while cur_b:\n",
    "            if cur_b in dic:\n",
    "                return cur_b\n",
    "            cur_b = cur_b.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not(headA and headB):\n",
    "            return None\n",
    "        node_set  = set()\n",
    "        headA_copy = headA\n",
    "        while headA_copy:\n",
    "            node_set.add(headA_copy)\n",
    "            headA_copy = headA_copy.next\n",
    "        headB_copy = headB\n",
    "        while headB_copy:\n",
    "            if headB_copy in node_set:\n",
    "                return headB_copy\n",
    "            headB_copy= headB_copy.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        dummy_headA = ListNode(next = headA)\n",
    "        dummy_headB = ListNode(next = headB)\n",
    "        curA = headA\n",
    "        curB = headB\n",
    "        m = 0\n",
    "        n = 0\n",
    "        while(dummy_headA.next):\n",
    "            dummy_headA = dummy_headA.next\n",
    "            m += 1\n",
    "        while(dummy_headB.next):\n",
    "            dummy_headB = dummy_headB.next\n",
    "            n += 1\n",
    "        if m > n:\n",
    "            for i in range(m-n):\n",
    "                curA = curA.next\n",
    "        if m < n:\n",
    "            for i in range(n-m):\n",
    "                curB = curB.next\n",
    "        while curA:\n",
    "            if curA == curB:\n",
    "                return curA\n",
    "            else:\n",
    "                curA = curA.next\n",
    "                curB = curB.next\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        A, B = headA, headB\n",
    "        while A != B:\n",
    "            if A:\n",
    "                A = A.next\n",
    "            else:\n",
    "                A = headB\n",
    "            if B:\n",
    "                B = B.next\n",
    "            else:\n",
    "                B= headA\n",
    "        return A\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        # if not headA or not headB:\n",
    "        #     return None\n",
    "\n",
    "        # a,b = headA,headB\n",
    "        # while a != b:\n",
    "        #     a = a.next if a else headB\n",
    "        #     b = b.next if b else headA\n",
    "        # return a \n",
    "        lena = lenb = 0\n",
    "        cur = headA\n",
    "        while cur:\n",
    "            lena+=1\n",
    "            cur = cur.next\n",
    "        cur = headB\n",
    "        while cur:\n",
    "            lenb+=1\n",
    "            cur = cur.next\n",
    "        cura,curb = headA,headB\n",
    "        if lena>lenb:\n",
    "            cura,curb = curb,cura\n",
    "            lena,lenb = lenb,lena\n",
    "        for i in range(lenb - lena):\n",
    "            curb = curb.next\n",
    "        while cura:\n",
    "            if cura == curb:\n",
    "                return cura\n",
    "            else:\n",
    "                cura = cura.next\n",
    "                curb = curb.next\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        lenA,lenB=0,0\n",
    "        cur=headA\n",
    "        while cur:\n",
    "            cur=cur.next\n",
    "            lenA+=1\n",
    "        cur=headB\n",
    "        while cur:\n",
    "            cur=cur.next\n",
    "            lenB+=1\n",
    "        curA,curB=headA,headB\n",
    "        if lenA>lenB:\n",
    "            curA,curB=curB,curA\n",
    "            lenA,lenB=lenB,lenA\n",
    "        for _ in range(lenB-lenA):\n",
    "            curB=curB.next\n",
    "        while curA:\n",
    "            if curA==curB:\n",
    "                return curA\n",
    "            else: \n",
    "                curA=curA.next\n",
    "                curB=curB.next\n",
    "        return None\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        a,b=headA,headB\n",
    "        while a!=b:\n",
    "            a=a.next if a else headB\n",
    "            b=b.next if b else headA\n",
    "        return a\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        #等比例法\n",
    "        if not headA or not headB:\n",
    "            return None\n",
    "        headA1 = headA\n",
    "        headB1 = headB\n",
    "        while headA1 != headB1:\n",
    "            headA1 = headA1.next if headA1 else headB\n",
    "            headB1 = headB1.next if headB1 else headA\n",
    "        return headA1\n",
    "\n",
    "        #比较麻烦算法\n",
    "        # lenA = lenB = 0\n",
    "        # headA1 = headA\n",
    "        # headB1 = headB\n",
    "        # while headA1:\n",
    "        #     headA1 = headA1.next\n",
    "        #     lenA += 1\n",
    "        # while headB1:\n",
    "        #     headB1 = headB1.next\n",
    "        #     lenB += 1\n",
    "        # if lenA > lenB:\n",
    "        #     for i in range(lenA-lenB):\n",
    "        #         headA = headA.next\n",
    "        # else:\n",
    "        #     for i in range(lenB-lenA):\n",
    "        #         headB = headB.next\n",
    "        # while headA != headB:\n",
    "        #     headA = headA.next\n",
    "        #     headB = headB.next\n",
    "        # return headA\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if headA is None or headB is None:\n",
    "            return None\n",
    "        ptr_a, ptr_b = headA, headB\n",
    "        isARepeat, isBRepeat = False, False\n",
    "        while ptr_a != ptr_b:\n",
    "            try:\n",
    "                ptr_a = ptr_a.next\n",
    "            except Exception:\n",
    "                if not isARepeat:\n",
    "                    ptr_a = headB\n",
    "                    isARepeat = not isARepeat\n",
    "                else:\n",
    "                    return None    \n",
    "            try:\n",
    "                ptr_b = ptr_b.next\n",
    "            except Exception:\n",
    "                if not isBRepeat:\n",
    "                    ptr_b = headA\n",
    "                    isBRepeat = not isBRepeat\n",
    "                else:\n",
    "                    return None\n",
    "        return ptr_a\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        '''\n",
    "        这个方法比较巧妙。利用双指针同时移动，在到尾部的时候就交换位置\n",
    "        因为移动距离相同，如果有交点一定会在交点处相交。这个可以在数学上证明\n",
    "        a:      A ------- C --------- B\n",
    "        b: E -- A ------- C --------- D\n",
    "        设交点为 C 则有:\n",
    "        L(a) = AB + EC\n",
    "        L(b) = ED + AC\n",
    "\n",
    "        ED + AC - (AB + EC) = ED + AC - AB - (EA + AC) = ED - AB - EA\n",
    "        = ED = (EA + AB) = 0\n",
    "        '''\n",
    "        if not headA or not headB:\n",
    "            return None\n",
    "        pa, pb = headA, headB\n",
    "        while pa != pb:\n",
    "            if pa is None:\n",
    "                pa = headB\n",
    "            else:\n",
    "                pa = pa.next\n",
    "            if pb is None:\n",
    "                pb = headA\n",
    "            else:\n",
    "                pb = pb.next\n",
    "        return pa\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        cura, curb = headA, headB\n",
    "        while cura != curb:\n",
    "            cura = cura.next if cura else headB\n",
    "            curb = curb.next if curb else headA\n",
    "        \n",
    "        return cura\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        sizeA = sizeB = 0\n",
    "        currentA = headA\n",
    "        currentB = headB\n",
    "\n",
    "        while currentA:\n",
    "            sizeA += 1\n",
    "            currentA = currentA.next \n",
    "        \n",
    "        while currentB:\n",
    "            sizeB += 1\n",
    "            currentB = currentB.next\n",
    "        \n",
    "        dummy_headA = ListNode(next = headA)\n",
    "        dummy_headB = ListNode(next = headB)\n",
    "        currentA = dummy_headA\n",
    "        currentB = dummy_headB\n",
    "        \n",
    "        if sizeA >= sizeB:\n",
    "            n = sizeA - sizeB\n",
    "            while n > 0:\n",
    "                currentA = currentA.next\n",
    "                n -= 1\n",
    "        else:\n",
    "            n = sizeB - sizeA\n",
    "            while n > 0:\n",
    "                currentB = currentB.next\n",
    "                n -= 1\n",
    "        \n",
    "        while currentA:\n",
    "            if currentA == currentB:\n",
    "                return currentA\n",
    "            currentA = currentA.next\n",
    "            currentB = currentB.next\n",
    "            \n",
    "        \n",
    "        return \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:\n",
    "            return None\n",
    "        pA, pB = headA, headB\n",
    "        while pB != pA:\n",
    "            pA = pA.next if pA else headB\n",
    "            pB = pB.next if pB else headA\n",
    "        return pA\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        A, B = headA, headB\n",
    "        while A != B:\n",
    "            A = A.next if A else headB\n",
    "            B = B.next if B else headA\n",
    "        return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if(headA==None or headB==None):\n",
    "            return None\n",
    "\n",
    "\n",
    "        def forword(pa,step):\n",
    "            head = pa\n",
    "            for i in range(step):\n",
    "                head=head.next\n",
    "            return head\n",
    "\n",
    "\n",
    "        def getLenth(pa):\n",
    "            length = 0\n",
    "            cur = pa    \n",
    "            while(cur):\n",
    "                length += 1\n",
    "                cur = cur.next\n",
    "            return length\n",
    "\n",
    "        lenA = getLenth(headA)\n",
    "        lenB = getLenth(headB)\n",
    "        print(lenA,lenB)\n",
    "\n",
    "        if(lenA > lenB):\n",
    "            headA = forword(headA,lenA-lenB)\n",
    "        else:\n",
    "            headB = forword(headB,lenB-lenA)\n",
    "        print(headB.val)\n",
    "        while(headA != None):\n",
    "            if(headA == headB):\n",
    "                return headA\n",
    "            headA=headA.next\n",
    "            headB=headB.next\n",
    "        return None\n",
    "\n",
    "\n",
    "\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        \"\"\"\n",
    "        寻找两个链表相交的节点，若存在则返回该节点，不存在返回None\n",
    "        :param headA:链表A的头结点\n",
    "        :param headB:链表B的头结点\n",
    "        :return:若存在则返回该节点，不存在返回None\n",
    "        \"\"\"\n",
    "        cura = headA  # 从头结点开始记录链表A的节点数\n",
    "        numa = 0  # 链表A的节点数\n",
    "        while cura:\n",
    "            cura = cura.next\n",
    "            numa += 1\n",
    "        curb = headB  # 从头结点开始记录链表B的节点数\n",
    "        numb = 0  # 链表A的节点数\n",
    "        while curb:\n",
    "            curb = curb.next\n",
    "            numb += 1\n",
    "        cura = headA  # 从头结点开始同步\n",
    "        curb = headB\n",
    "        if numa > numb:\n",
    "            l = numa-numb # 计算两个链表的节点数差，方便后续同步移动\n",
    "            for i in range(l):\n",
    "                cura = cura.next  # A长就向后移\n",
    "        else:\n",
    "            l = numb - numa\n",
    "            for i in range(l):\n",
    "                curb = curb.next  # B长就向后移\n",
    "        while cura:  # 一个一个对比直到尾节点\n",
    "            if cura == curb:  # 相同则返回指针\n",
    "                return cura\n",
    "            else:  # 逐步后移\n",
    "                cura = cura.next\n",
    "                curb = curb .next\n",
    "        return None  # 找不到相同则返回None\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        ta = headA\n",
    "        tb = headB\n",
    "        while ta != tb:\n",
    "            #此时两个链表经历两边 步数相同，如果此时为空，则代表不会相交\n",
    "            if not ta:\n",
    "                ta = headB\n",
    "            else:\n",
    "                ta = ta.next\n",
    "            if not tb:\n",
    "                tb = headA\n",
    "            else:\n",
    "                tb = tb.next\n",
    "        return ta "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        cur_a,cur_b=headA,headB\n",
    "        while cur_a != cur_b:\n",
    "            if cur_a==None:\n",
    "                cur_a=headB\n",
    "            else:\n",
    "                cur_a=cur_a.next\n",
    "\n",
    "            if cur_b==None:\n",
    "                cur_b=headA\n",
    "            else:\n",
    "                cur_b=cur_b.next\n",
    "            \n",
    "        return cur_a\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        #1、求出两个链表的长度\n",
    "        lenA = self.getLength(headA)\n",
    "        lenB = self.getLength(headB)\n",
    "        #2、求出两个链表长度的差值\n",
    "        if lenA - lenB>0:\n",
    "            headA = self.getForward(lenA-lenB,headA)\n",
    "        else:\n",
    "            headB = self.getForward(lenB-lenA,headB)\n",
    "            \n",
    "        while headA and headB:\n",
    "            if headA == headB:\n",
    "                return headA\n",
    "            else:\n",
    "                headA = headA.next\n",
    "                headB = headB.next\n",
    "        return None\n",
    "        \n",
    "\n",
    "    #1、求出链表的长度\n",
    "    def getLength(self,head):\n",
    "        cur = head\n",
    "        len = 0\n",
    "        while cur:\n",
    "            cur =cur.next\n",
    "            len+=1\n",
    "        return len\n",
    "    #2、向前移动两个链表的差值\n",
    "    def getForward(self,step,head):\n",
    "        pre = head\n",
    "        for _ in range(step):\n",
    "            pre = pre.next\n",
    "        return pre\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        def getLength(head: ListNode) -> int:\n",
    "            len = 0\n",
    "            while head:\n",
    "                len += 1\n",
    "                head = head.next\n",
    "            return len\n",
    "        newA, newB = headA, headB\n",
    "        lenA, lenB = getLength(headA), getLength(headB)\n",
    "        while lenA > lenB:\n",
    "            newA = newA.next\n",
    "            lenA -= 1\n",
    "        while lenB > lenA:\n",
    "            newB = newB.next\n",
    "            lenB -= 1\n",
    "        while newA and newA != newB:\n",
    "            newA = newA.next\n",
    "            newB = newB.next\n",
    "        return newA\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        na,nb=0,0\n",
    "        cura=headA\n",
    "        curb=headB\n",
    "\n",
    "        while cura:\n",
    "            cura=cura.next\n",
    "            na+=1\n",
    "        while curb:\n",
    "            curb=curb.next\n",
    "            nb+=1\n",
    "        \n",
    "        cura,curb=headA,headB       \n",
    "        \n",
    "        if na >= nb:\n",
    "            for i in range(na-nb):\n",
    "                cura=cura.next\n",
    "        else:\n",
    "            for i in range(nb-na):\n",
    "                curb=curb.next\n",
    "                \n",
    "        while cura!=curb:\n",
    "            cura=cura.next\n",
    "            curb=curb.next\n",
    "        return cura\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        \n",
    "        # 原理是底部对齐后找到相等的元素即为相交元素\n",
    "\n",
    "        headA_ = headA\n",
    "        headB_ = headB\n",
    "\n",
    "        # 如果不想交最后都为None\n",
    "        while headA_ != headB_:\n",
    "            headA_ = headA_.next if headA_ else headB\n",
    "            headB_ = headB_.next if headB_ else headA\n",
    "\n",
    "        return headA_\n",
    "\n",
    "\n",
    "        # # 寻找特征值\n",
    "        # inter_node = None\n",
    "        # headA_ = headA\n",
    "        # while headA_:\n",
    "        #     headA_.val *= -1\n",
    "        #     headA_ = headA_.next\n",
    "\n",
    "        # headB_ = headB\n",
    "        # while headB_:\n",
    "        #     if headB_.val < 0:\n",
    "        #         inter_node = headB_\n",
    "        #         break\n",
    "\n",
    "        #     headB_ = headB_.next\n",
    "\n",
    "        # headA_ = headA\n",
    "        # while headA_:\n",
    "        #     headA_.val *= -1\n",
    "        #     headA_ = headA_.next\n",
    "\n",
    "        # return inter_node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        lenA = 0\n",
    "        lenB = 0\n",
    "        curA = headA\n",
    "        curB = headB\n",
    "        while curA:\n",
    "            curA = curA.next\n",
    "            lenA += 1\n",
    "        while curB:\n",
    "            curB = curB.next\n",
    "            lenB += 1\n",
    "\n",
    "        if lenB > lenA:\n",
    "            lenA, lenB = lenB, lenA\n",
    "            headA, headB = headB, headA\n",
    "\n",
    "        curA = headA\n",
    "        curB = headB\n",
    "        while lenA - lenB > 0:\n",
    "            curA = curA.next\n",
    "            lenA -= 1\n",
    "            \n",
    "        while curB != curA:\n",
    "            curA = curA.next\n",
    "            curB = curB.next\n",
    "\n",
    "        return curA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        lenA = lenB = 0\n",
    "        currentA = headA\n",
    "        currentB = headB\n",
    "        while currentA != None:\n",
    "            lenA += 1\n",
    "            currentA = currentA.next\n",
    "        while currentB != None:\n",
    "            lenB += 1\n",
    "            currentB = currentB.next\n",
    "        curA = headA\n",
    "        curB = headB\n",
    "        if lenA > lenB:\n",
    "            curA, curB = curB, curA\n",
    "            lenA, lenB = lenB, lenA\n",
    "        for _ in range(lenB-lenA):\n",
    "            curB = curB.next\n",
    "        while curA:\n",
    "            if curA == curB:\n",
    "                return curA\n",
    "            else:\n",
    "                curA = curA.next\n",
    "                curB = curB.next\n",
    "        return None\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        a, b = 0,0\n",
    "        cur = headA\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            a+=1\n",
    "        cur = headB\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            b+=1\n",
    "        curA, curB = headA, headB\n",
    "        if a >b:\n",
    "            curA, curB = curB, curA\n",
    "            a, b = b,a \n",
    "        for _ in range(b-a):\n",
    "            curB = curB.next\n",
    "        while curA:\n",
    "            if curA == curB:\n",
    "                return curA\n",
    "            else:\n",
    "                curA = curA.next\n",
    "                curB = curB.next\n",
    "        return None\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        \"\"\"\n",
    "        寻找两个链表相交的节点，若存在则返回该节点，不存在返回None\n",
    "        :param headA:链表A的头结点\n",
    "        :param headB:链表B的头结点\n",
    "        :return:若存在则返回该节点，不存在返回None\n",
    "        \"\"\"\n",
    "        cura = headA  # 从头结点开始记录链表A的节点数\n",
    "        numa = 0  # 链表A的节点数\n",
    "        while cura:\n",
    "            cura = cura.next\n",
    "            numa += 1\n",
    "        curb = headB  # 从头结点开始记录链表B的节点数\n",
    "        numb = 0  # 链表A的节点数\n",
    "        while curb:\n",
    "            curb = curb.next\n",
    "            numb += 1\n",
    "        cura = headA\n",
    "        curb = headB\n",
    "        if numa > numb:\n",
    "            l = numa-numb # 计算两个链表的节点数差，方便后续同步移动\n",
    "            for i in range(l):\n",
    "                cura = cura.next\n",
    "        else:\n",
    "            l = numb - numa\n",
    "            for i in range(l):\n",
    "                curb = curb.next\n",
    "        while cura :\n",
    "            if cura == curb:\n",
    "                return cura\n",
    "            else:\n",
    "                cura = cura.next\n",
    "                curb = curb .next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        lenA, lenB = 0, 0\n",
    "        cur = headA\n",
    "        while cur:         # 求链表A的长度\n",
    "            cur = cur.next \n",
    "            lenA += 1\n",
    "        cur = headB\n",
    "        while cur:         # 求链表B的长度\n",
    "            cur = cur.next \n",
    "            lenB += 1\n",
    "        curA, curB = headA, headB\n",
    "        if lenA < lenB:\n",
    "            curA, curB = curB, curA\n",
    "            lenA, lenB = lenB, lenA\n",
    "        for i in range(lenA - lenB):\n",
    "            curA = curA.next\n",
    "        while curA:\n",
    "            if curA == curB:\n",
    "                return curA\n",
    "            else:\n",
    "                curA = curA.next\n",
    "                curB = curB.next\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        \n",
    "        inter_node = None\n",
    "\n",
    "        headA_ = headA\n",
    "        while headA_:\n",
    "            headA_.val *= -1\n",
    "            headA_ = headA_.next\n",
    "\n",
    "        headB_ = headB\n",
    "        while headB_:\n",
    "            if headB_.val < 0:\n",
    "                inter_node = headB_\n",
    "                break\n",
    "\n",
    "            headB_ = headB_.next\n",
    "\n",
    "        headA_ = headA\n",
    "        while headA_:\n",
    "            headA_.val *= -1\n",
    "            headA_ = headA_.next\n",
    "\n",
    "        return inter_node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        pa = headA\n",
    "        pb = headB\n",
    "        while headA or headB:\n",
    "            if headA == headB:\n",
    "                return headA\n",
    "            if not headA:\n",
    "                headA = pb\n",
    "                headB = headB.next\n",
    "                continue\n",
    "            if not headB:\n",
    "                headB = pa\n",
    "                headA = headA.next\n",
    "                continue\n",
    "            headA = headA.next\n",
    "            headB = headB.next\n",
    "        return None\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        cur1=headA\n",
    "        cur2=headB\n",
    "        s1=0\n",
    "        s2=0\n",
    "        while cur1:\n",
    "            s1=s1+1\n",
    "            cur1=cur1.next\n",
    "        \n",
    "        while cur2:\n",
    "            s2=s2+1\n",
    "            cur2=cur2.next    \n",
    "        if s1-s2>=0:\n",
    "            n=s1-s2\n",
    "            cur3=headA\n",
    "            cur4=headB\n",
    "        else:\n",
    "            n=s2-s1\n",
    "            cur3=headB\n",
    "            cur4=headA\n",
    "\n",
    "        for i in range(n):\n",
    "            cur3=cur3.next\n",
    "            \n",
    "        while cur3:       #####遍历\n",
    "            if cur3==cur4:\n",
    "                return cur3\n",
    "            else:\n",
    "                cur3=cur3.next\n",
    "                cur4=cur4.next\n",
    "        return None \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        length_A = self.getLength(headA)\n",
    "        length_B = self.getLength(headB)\n",
    "\n",
    "        if length_A - length_B > 0:\n",
    "            distance = length_A - length_B\n",
    "            headA = self.MoveForward(headA, distance)\n",
    "        else:\n",
    "            distance = length_B - length_A\n",
    "            headB = self.MoveForward(headB, distance)\n",
    "        \n",
    "        while headA and headB:\n",
    "            if headA == headB:\n",
    "                return headA\n",
    "            headA = headA.next\n",
    "            headB = headB.next\n",
    "        \n",
    "        return None\n",
    "    \n",
    "    def getLength(self, head):\n",
    "        length = 0\n",
    "        while head:\n",
    "            head = head.next\n",
    "            length += 1\n",
    "        return length\n",
    "    \n",
    "    def MoveForward(self, head, distance):\n",
    "        for i in range(distance):\n",
    "            head = head.next\n",
    "        return head\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        A = headA\n",
    "        B = headB\n",
    "        while A != B :\n",
    "            A = A.next if A else headB\n",
    "            B = B.next if B else headA\n",
    "        return A\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if headA is None or headB is None:\n",
    "            return None\n",
    "        \n",
    "        lenA, lenB = 0, 0\n",
    "\n",
    "        tmpheadA = headA\n",
    "        tmpheadB = headB\n",
    "\n",
    "        while tmpheadA:\n",
    "            lenA += 1\n",
    "            tmpheadA = tmpheadA.next\n",
    "        \n",
    "        while tmpheadB:\n",
    "            lenB += 1\n",
    "            tmpheadB = tmpheadB.next\n",
    "        \n",
    "        diff = abs(lenA - lenB)\n",
    "\n",
    "        if lenA > lenB:\n",
    "            while diff > 0:\n",
    "                headA = headA.next\n",
    "                diff -= 1\n",
    "            \n",
    "            while headA and headB:\n",
    "                if headA == headB:\n",
    "                    return headA\n",
    "                headA = headA.next\n",
    "                headB = headB.next\n",
    "        else:\n",
    "            while diff > 0:\n",
    "                headB = headB.next\n",
    "                diff -= 1\n",
    "            \n",
    "            while headA and headB:\n",
    "                if headA == headB:\n",
    "                    return headA\n",
    "                headA = headA.next\n",
    "                headB = headB.next\n",
    "\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        cura = headA\n",
    "        numa = 0\n",
    "        while cura:\n",
    "            cura = cura.next\n",
    "            numa += 1\n",
    "        curb = headB\n",
    "        numb = 0\n",
    "        while curb:\n",
    "            curb = curb.next\n",
    "            numb += 1\n",
    "        if numa > numb:\n",
    "            l = numa-numb\n",
    "            cura = headA\n",
    "            curb = headB\n",
    "            for i in range(l):\n",
    "                cura = cura.next\n",
    "        else:\n",
    "            l = numb - numa\n",
    "            cura = headA\n",
    "            curb = headB\n",
    "            for i in range(l):\n",
    "                curb = curb.next\n",
    "        while cura :\n",
    "            if cura == curb:\n",
    "                return cura\n",
    "            else:\n",
    "                cura = cura.next\n",
    "                curb = curb .next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        lenA = 0\n",
    "        lenB = 0\n",
    "        dummy1 = ListNode(0)\n",
    "        dummy1.next = headA\n",
    "        curA = dummy1\n",
    "        while curA != None:\n",
    "            curA = curA.next\n",
    "            lenA += 1\n",
    "        dummy2 = ListNode(0)\n",
    "        dummy2.next = headB\n",
    "        curB = dummy2\n",
    "        while curB != None:\n",
    "            curB = curB.next\n",
    "            lenB += 1\n",
    "        # print('length',lenA, lenB)\n",
    "        lenA -= 1\n",
    "        lenB -= 1\n",
    "        print('length',lenA, lenB)\n",
    "        if lenA >= lenB:\n",
    "            curA = dummy1\n",
    "            curB = dummy2\n",
    "            for i in range(lenA - lenB):\n",
    "                curA = curA.next\n",
    "            print('here')\n",
    "        else:\n",
    "            curA = dummy1\n",
    "            curB = dummy2\n",
    "            for i in range(lenB - lenA):\n",
    "                curB = curB.next\n",
    "        while curA != None:\n",
    "            if curA == curB:\n",
    "                return curA\n",
    "            else:\n",
    "                curA = curA.next\n",
    "                curB = curB.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        cura = headA\n",
    "        curb = headB\n",
    "        if cura == curb:\n",
    "            return cura\n",
    "        counta = 0\n",
    "        countb = 0\n",
    "        while cura:\n",
    "            cura = cura.next\n",
    "            counta += 1\n",
    "        while curb:\n",
    "            curb = curb.next\n",
    "            countb += 1\n",
    "        cura = headA\n",
    "        curb = headB\n",
    "        if counta >= countb:\n",
    "            dif = counta - countb\n",
    "            for i in range(dif):\n",
    "                cura = cura.next\n",
    "        else:\n",
    "            dif = countb - counta \n",
    "            for i in range(dif):\n",
    "                curb = curb.next \n",
    "        while cura:\n",
    "            if cura != None and cura == curb:\n",
    "                return cura\n",
    "            cura = cura.next\n",
    "            curb = curb.next\n",
    "            \n",
    "        return None\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA and not headB:\n",
    "            return None\n",
    "        \n",
    "        pA, pB = headA, headB\n",
    "        while pA != pB:\n",
    "            pA = pA.next if pA else headB\n",
    "            pB = pB.next if pB else headA\n",
    "        return pA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        lenA = self.getLength(headA)\n",
    "        lenB = self.getLength(headB)\n",
    "\n",
    "        if lenA > lenB:\n",
    "            headA = self.moveForward(headA, lenA - lenB)\n",
    "        else:\n",
    "            headB = self.moveForward(headB, lenB - lenA)\n",
    "        \n",
    "        while headA and headB:\n",
    "            if headA == headB:\n",
    "                return headA\n",
    "            headA = headA.next\n",
    "            headB = headB.next\n",
    "        return None\n",
    "    \n",
    "    def getLength(self, head):\n",
    "        length = 0\n",
    "        while head:\n",
    "            length += 1\n",
    "            head = head.next\n",
    "        return length\n",
    "\n",
    "    def moveForward(self, head, steps):\n",
    "        while steps > 0:\n",
    "            head = head.next\n",
    "            steps -= 1\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        lenA = self.getLength(headA)\n",
    "        lenB = self.getLength(headB)\n",
    "\n",
    "        if lenA > lenB:\n",
    "            headA = self.moveForward(headA, lenA - lenB)\n",
    "        else:\n",
    "            headB = self.moveForward(headB, lenB - lenA)\n",
    "        \n",
    "        while headA and headB:\n",
    "            if headA == headB:\n",
    "                return headA\n",
    "            headA = headA.next\n",
    "            headB = headB.next\n",
    "        return None\n",
    "    \n",
    "    def getLength(self, head):\n",
    "        length = 0\n",
    "        while head:\n",
    "            length += 1\n",
    "            head = head.next\n",
    "        return length\n",
    "\n",
    "    def moveForward(self, head, steps):\n",
    "        while steps > 0:\n",
    "            head = head.next\n",
    "            steps -= 1\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA and not headB:\n",
    "            return \n",
    "        \n",
    "        pA, pB = headA, headB\n",
    "        while pA != pB:\n",
    "            pA = pA.next if pA else headB\n",
    "            pB = pB.next if pB else headA\n",
    "        # pA走一遍链表A后在链表B中循环\n",
    "        # pB走一遍链表B后在链表A中循环\n",
    "        # 若两个链表不相交，pA，pB各把两个链表走一遍，最后都为None\n",
    "        # 若两个链表相交，则pA和pB终究在交点相遇\n",
    "        return pA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        la=lb=0\n",
    "        ha,hb=headA,headB\n",
    "        while ha:\n",
    "            la+=1\n",
    "            ha=ha.next\n",
    "        while hb:\n",
    "            lb+=1\n",
    "            hb=hb.next\n",
    "        ha,hb=headA,headB\n",
    "        if lb>la:\n",
    "            while lb-la:\n",
    "                hb=hb.next\n",
    "                lb-=1\n",
    "        else:\n",
    "            while la-lb:\n",
    "                ha=ha.next\n",
    "                la-=1\n",
    "        while ha:\n",
    "            if ha==hb:\n",
    "                return ha\n",
    "            ha=ha.next\n",
    "            hb=hb.next\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:\n",
    "            return None\n",
    "\n",
    "        p1 = headA\n",
    "        p2 = headB\n",
    "\n",
    "        while p1 or p2:\n",
    "            if p1 == p2:\n",
    "                return p1\n",
    "            if not p1.next and not p2.next:\n",
    "                return p1 if p1 == p2 else None\n",
    "            p1 = p1.next if p1.next else headB\n",
    "            p2 = p2.next if p2.next else headA\n",
    "\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        curA,curB = headA,headB\n",
    "        lA,lB = 0,0\n",
    "        while curA:\n",
    "            lA+=1\n",
    "            curA = curA.next\n",
    "        while curB:\n",
    "            lB+=1\n",
    "            curB = curB.next\n",
    "        \n",
    "        while lA>lB:\n",
    "            headA = headA.next\n",
    "            lA-=1\n",
    "\n",
    "        while lB>lA:\n",
    "            headB = headB.next\n",
    "            lB-=1\n",
    "\n",
    "        while headA and headB:\n",
    "            if headA == headB:\n",
    "                return headA\n",
    "            headA = headA.next\n",
    "            headB = headB.next\n",
    "        \n",
    "        return None\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        def getLength(head):\n",
    "            length = 0\n",
    "            while head:\n",
    "                length += 1\n",
    "                head = head.next\n",
    "            return length\n",
    "        lengthA = getLength(headA)\n",
    "        lengthB = getLength(headB)\n",
    "\n",
    "        curA = headA\n",
    "        curB = headB\n",
    "\n",
    "        if lengthA > lengthB:\n",
    "            curA, curB = curB, curA\n",
    "            lengthA, lengthB = lengthB, lengthA\n",
    "        \n",
    "        for _ in range(lengthB-lengthA):\n",
    "            curB = curB.next\n",
    "\n",
    "        while curA:\n",
    "            if curA == curB:\n",
    "                return curA\n",
    "            else:\n",
    "                curA = curA.next\n",
    "                curB = curB.next\n",
    "        return None\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        head = headA\n",
    "        lenA = 0\n",
    "        lenB = 0\n",
    "        while head:\n",
    "            lenA += 1\n",
    "            head = head.next\n",
    "        head = headB\n",
    "        while head:\n",
    "            lenB += 1\n",
    "            head = head.next\n",
    "        curA = headA\n",
    "        curB = headB\n",
    "        if lenA >lenB:\n",
    "            curA,curB = curB,curA\n",
    "            lenA,lenB = lenB,lenA\n",
    "        len = lenB-lenA\n",
    "        for i in range(len):\n",
    "            curB = curB.next\n",
    "        while curB:\n",
    "            if curA != curB:\n",
    "                curA = curA.next\n",
    "                curB = curB.next\n",
    "            else:\n",
    "                return curA\n",
    "        return None\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        def getsize(head):\n",
    "            size=1\n",
    "            cur=head\n",
    "            if cur==None:\n",
    "                return 0\n",
    "            while cur.next!=None:\n",
    "                cur=cur.next\n",
    "                size+=1\n",
    "            return size\n",
    "        sizeA=getsize(headA)\n",
    "        sizeB=getsize(headB)\n",
    "        curA=headA\n",
    "        curB=headB\n",
    "        if sizeA>sizeB:\n",
    "            for i in range(abs(sizeA-sizeB)):\n",
    "                curA=curA.next\n",
    "        else:\n",
    "            for i in range(abs(sizeA-sizeB)):\n",
    "                curB=curB.next  \n",
    "        while curA!=None:\n",
    "            if curA==curB:\n",
    "                return curA\n",
    "            else:\n",
    "                curA=curA.next\n",
    "                curB=curB.next\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        lenA = self.getLength(headA)\n",
    "        lenB = self.getLength(headB)\n",
    "\n",
    "        if lenA > lenB:\n",
    "            headA = self.moveForward(headA, lenA - lenB)\n",
    "        else:\n",
    "            headB = self.moveForward(headB, lenB - lenA)\n",
    "        \n",
    "        while headA and headB:\n",
    "            if headA == headB:\n",
    "                return headA\n",
    "            headA = headA.next\n",
    "            headB = headB.next\n",
    "        return None\n",
    "    \n",
    "    def getLength(self, head):\n",
    "        length = 0\n",
    "        while head:\n",
    "            length += 1\n",
    "            head = head.next\n",
    "        return length\n",
    "\n",
    "    def moveForward(self, head, steps):\n",
    "        while steps > 0:\n",
    "            head = head.next\n",
    "            steps -= 1\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        A,B = headA,headB\n",
    "        while A!=B:\n",
    "            A = A.next if A else headB\n",
    "            B = B.next if B else headA\n",
    "        return A \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
